
//1818.绝对差值和
class Solution {
    #define MOD 1000000007
    int near(vector<int>& nums,int target)
    {
        int pos=lower_bound(nums.begin(),nums.end(),target)-nums.begin();
        if(pos==nums.size()) return target-nums[pos-1];

        int prev=pos-1,tmp=0;
        if(prev>=0&&target-nums[prev]<nums[pos]-target) return target-nums[prev];
        else return nums[pos]-target;
    }

public:
    int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) {
        //遍历数组找到数组中绝对差最大的位置

        vector<int> tmp1(nums1);
        vector<int> tmp2(nums2);
        //对两个数组进行排序
        sort(tmp1.begin(),tmp1.end());        
        sort(tmp2.begin(),tmp2.end());    

        int n=nums1.size(),less=0;  //less记录通过改变nums1的一个元素能够影响ret的最大值
        long long ret=0;
        for(int i=0;i<n;i++) 
        {
            int div=abs(nums1[i]-nums2[i]);
            if(div>less)
            {
                //在nums1中找最接近nums2[i]的位置
                int l=near(tmp1,nums2[i]);

                less=max(div-l,less);
            }
            ret+=div;
        }
        
        return (ret-less)%MOD;
    }
};